package com.leetcode.search.dfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/9/12 16:24
 */
public class ZeroAndOne_542 {

    int[][] directions = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

    public int[][] updateMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return null;

        int width = matrix[0].length, high = matrix.length;
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < high; i++) {
            for (int j = 0; j < width; j++) {
                if (matrix[i][j] == 0)
                    queue.offer(new int[]{i, j});
                else
                    matrix[i][j] = -1;
            }
        }

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int i = now[0], j = now[1];
            for (int[] d : directions) {
                int y = i + d[0], x = j + d[1];
                if (x >= 0 && x < width && y >= 0 && y < high
                    && matrix[y][x] == -1) {
                    matrix[y][x] = matrix[i][j] + 1;
                    queue.offer(new int[]{y, x});
                }
            }
        }

        return matrix;
    }

}
